package com.ming.learn.from.carl.hash;

import java.util.HashMap;

/*
第454题.四数相加II
 */
public class Of20201223LeetCode454 {
    /*
    本题解题步骤：
    首先定义 一个unordered_map，key放a和b两数之和，value 放a和b两数之和出现的次数。
    遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中。
    定义int变量count，用来统计a+b+c+d = 0 出现的次数。
    在遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就用count把map中key对应的value也就是出现次数统计出来。
    最后返回统计值 count 就可以了
     */
    static int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int count = 0;
        for (int a : A) {
            for (int b : B) {
                int i = 1;
                if (map.containsKey(a + b)) {
                    i = map.get(a + b);
                    i++;
                }
                map.put(a + b, i);
            }
        }
        for (int c : C) {
            for (int d : D) {
                if (map.containsKey(-c - d))
                    count += map.get(-c - d);
            }
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(fourSumCount(new int[]{1, 2}, new int[]{-2,-1}, new int[]{-1, 2}, new int[]{0, 2}));
    }
}
